package com.cn.algorithm02.class22;

/***
 * @author: hels
 * @description:
 *  货币数组arr，元素都是正数，每一个元素都看作是一张钱币；
 *  给定一个目标正数aim，返回arr中组成aim的方法数。
 *  例如;arr = {1,1,1} aim=2, 返回结果3种方法。
 *  </p>
 *  算法模型：
 *  1 从左到右尝试模型
 *  2 范围尝试模型
 *  3 样本对应模型
 *  4 业务限制模型
 **/
public class C02_CoinsWayEveryPapaerDifferent {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 4, 3, 1, 1};
        int aim = 5;
        System.out.println(process(arr, 0, aim));
        System.out.println(dp(arr, aim));
    }

    /**
     * 动态规划
     */
    public static int dp(int[] arr,  int aim) {
        int N =  arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N-1; index >= 0 ; index--) {
            for (int rest = 0; rest <= aim ; rest++) {
                dp[index][rest] = dp[index + 1][rest] + ( (rest - arr[index]) >= 0 ? dp[index + 1][rest - arr[index]] : 0);
            }
        }
        return dp[0][aim];
    }

    /**
     * 穷举法（暴力递归）
     * process(arr, index, rest) 从index到右正好组成rest值的方法有几个
     */
    public static int process(int[] arr, int index, int rest) {
        if (rest < 0) {
            return 0;
        }

        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }

        return process(arr, index + 1, rest - arr[index]) + process(arr, index + 1, rest);
    }
}
